package DoulblyLinked;

import linked.Node;

//将链表变为奇数偶数链表
public class EvenAndOddLinkedList {
    public static Node oddEvenList(Node head) {
        //头结点为空直接返回
        if (head == null) {
            return null;
        }

        //定义三个指针 odd指向奇数，even指向偶数，evenHead指向偶数的头结点
        Node odd = head, even = head.next, evenHead = even;
        //当前还有结束和偶数节点时
        while (even != null && even.next != null) {
            //将奇数节点的next指向偶数的next
            odd.next = even.next;
            //将奇数节点的指针向后移动一位，指向下一个奇数节点
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        node.next = new Node(2);
        node.next.next = new Node(3);
        node.next.next.next = new Node(4);
        node.next.next.next.next = new Node(5);
        node.next.next.next.next.next = new Node(6);
        node.next.next.next.next.next.next = new Node(7);
        node.next.next.next.next.next.next.next = new Node(8);
        node.next.next.next.next.next.next.next.next = new Node(null);

        while (node.next != null) {
            System.out.print(node.date + " ");
            node = node.next;
        }
        Node oddEvenList = oddEvenList(node);
        while (oddEvenList.next != null) {
            System.out.print(oddEvenList.date + " ");
            oddEvenList = oddEvenList.next;
        }

    }
}
